package leetcode;

import java.util.ArrayList;
import java.util.List;

/***
 * 题目：118. 杨辉三角
 * 链接：https://leetcode.cn/problems/pascals-triangle/description/
 * 题解：动态规划
 */
public class YangHuiSanJiao {
    public static void main(String[] args) {
        System.out.println(generate(5));
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for (int i = 1; i <= numRows; i++) {
            ArrayList<Integer> integers = new ArrayList<>();
            if (i == 1) {
                integers.add(0, 1);
                ans.add(0, integers);
            } else {
                List<Integer> list = ans.get(i - 2);
                integers.add(0, 1);
                for (int j = 1; j <= i - 2; j++) {
                    Integer i1 = list.get(j - 1);
                    Integer i2 = list.get(j);
                    integers.add(j, i1 + i2);
                }
                integers.add(i - 1, 1);
                ans.add(i - 1, integers);
            }
        }
        return ans;
    }
}
